In the field of parallel processing, the synchronization of many processors working on the same task is an important consideration. If not done efficiently, the synchronization task can over-burden the communication network and greatly reduce the effectiveness of parallel processing or add excessive cost.
One synchronization approach discussed widely in the literature is Barrier Synchronization. With this approach, each processing node can be allowed to free-run and can keep track of its own local time and synchronize with the other processors at barriers which are defined under software control. With barrier synchronization, the processors proceed until they reach a predefined barrier synchronization point. Any processor involved in a given barrier will proceed to the barrier and then wait at the barrier until all other processors involved have reached the barrier; then a new barrier is defined and the processors move toward it.
One very cumbersome drawback of the state-of-the-art barrier synchronization approaches is that the implementations can require a unique "BACKBONE" network, in addition to the normal message or data passing multi-stage switching network. Even worse, every "BACKBONE" network can only service one barrier at a time, so that a parallel system that requires many simultaneous barriers would have to implement many "BACKBONE" networks, which is both cumbersome and expensive.
It is important to handle synchronization techniques efficiently in parallel systems, and it is preferable to incorporate such synchronization in the normal communication networks that carry message traffic between processor nodes in a parallel system. Handling barriers over the normal data passing network saves the addition of new hardware between all nodes for synchronization. It is also preferable that barrier synchronization operations be able to have many different barriers active simultaneously--the more the better--and that there be a very inexpensive and efficient way of handling multiple barriers. The present invention presents a barrier synchronization method by which unlimited simultaneous barriers can all be processed efficiently over normal unbuffered multi-stage networks.